package summary;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/contains-duplicate-ii/
 */
public class Title219 {

    /**
     * 双指针(暴力，贼慢)
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length == 1 || k == 0) {
            return false;
        }
        for (int left = 0; left < nums.length; left++) {
            for (int right = left + 1; right < nums.length && right <= k + left; right++) {
                if (nums[left] == nums[right]) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 维持滑动窗口
     * @param nums
     * @param k
     * @return
     */
    public static boolean containsNearbyDuplicate1(int[] nums, int k) {
        if (nums.length == 1 || k == 0) {
            return false;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i < nums.length; i++) {
            if (i > k) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }

    /**
     * hashmap
     * @param nums
     * @param k
     * @return
     */
    public static boolean containsNearbyDuplicate2(int[] nums, int k) {
        if (nums.length == 1 || k == 0) {
            return false;
        }
        Map<Integer, Integer> hashmap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashmap.containsKey(nums[i]) && i - hashmap.get(nums[i]) <= k) {
                return true;
            }
            hashmap.put(nums[i], i);
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,1,2,3};
        int k = 2;
        containsNearbyDuplicate2(nums, k);
    }
}
